Relational and object-relational database management systems (hereafter “relational DBMS”) store information in tables of rows in a database. To retrieve data, queries that request data are submitted to a database server, which computes the queries and returns the data requested.
Query statements submitted to the database server should conform to the syntactical rules of a particular query language. One popular query language, known as the Structured Query Language (SQL), provides users a variety of ways to specify information to be retrieved.
Relational DBMSs may be enhanced to store XML data and are able to handle queries that use XML semantics to specify database operations, using XML query languages, such as XQuery and XPath. XML Query Language (“XQuery”) and XML Path Language (“XPath”) are important standards for a query language, and can be used in conjunction with SQL to express a large variety of useful queries. The term XML query is used to refer to queries that conform to SQL and/or XQuery, XPath, and/or another XML language standard, including proprietary dialects of XQuery, XPath, SQL, or XML standard languages. XML queries include SQL queries that embed XQuery and XPath expressions, XQuery queries that are not embedded within an SQL statement. When a relational DBMS receives a XML query, the database server may perform a XML rewrite to refer to the underlying base tables and database objects that store the XML data.
Query Optimizer
A query submitted to a database server is evaluated by a query optimizer. Based on the evaluation, the query optimizer generates an execution plan that defines operations for executing the query. Typically, the query optimizer generates an execution plan optimized for efficient execution. When a query optimizer evaluates a query, it determines various candidate execution plans” and selects an optimal execution plan.
During query optimization, different kinds of query transformations are performed. The query may be transformed into one or more semantically equivalent queries. A query is semantically equivalent to another when the queries request (or declare) the same results; computation of either should return the same result. A query may be computed more efficiently once transformed.
There are various kinds of transformations. For example, view merging is a type of transformation in which a subquery within the FROM clause (“inline view”) of the “outer query” is removed and is merged into the outer query to produce a semantically equivalent query.
The term kind or type of transformation, as used herein, refers transformations that are rewritten in a particular way or using specific types of rewrite operations.
Another type of rewrite is an XML rewrite. Typically, XML data is stored in underlying relational structures referred to as base structures. An XML rewrite rewrites expressions based on XML semantics (e.g. XPath and XQuery) into an expression that references the base structures.
A type of XML rewrite is an XML index rewrite. An XML index rewrite rewrites an XML query to refer to one or more structures of an XML index. An XML index is a “logical index” which indexes a collection of XML documents. A logical index contains multiple structures that are cooperatively used to access a collection of XML documents. A logical index includes a path table, which contains information about the hierarchies of nodes in a collection of XML documents and may contain the node values of the nodes. Among the columns or attributes of the path table is a column that stores the values of nodes, a pathid column that stores the path (in the form of a path id) of nodes, and a dewey_key column, which contains order keys that represent a hierarchical position of a node in a document, e.g. the order key value 3.21.5 specifies 5th child of 21st child of 3rd child of root.
An example of a XML index is described in Index For Accessing XML Data.
Order of Transformations
When determining how to optimize a query, many transformations and/or combinations of transforms can be applied. Applying a transformation consumes computer resources; doing this for all or even a proportion of all combinations of query transformations of a query may create a cost that is significant compared to the cost of computing the original query, if not more. To reduce costs of transforming queries, different types of transformations are applied in a predetermined order or sequence, referred to herein as a transformation sequence. The order in which the types of transformation are applied in a transformation sequence may be based on the way the kinds of transformations interact.
For example, an XML rewrite may create in an inline view, which can be merged using view merging. Thus, in a transformation sequence, an XML rewrite of a query is applied before view merging so that the view merge merges the inline view generated by the XML rewrite.
In general, a query optimizer generates optimized execution plans when the query optimizer is able to perform more kinds of transformations under more kinds of conditions.
The approaches described in this section are approaches that could be pursued, but not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section.